package main.java;

/**
 * @program: pratice
 * @author: 关键我是大怪
 * @create: 2021-11-05 19:11
 */

import java.util.HashMap;
import java.util.Map;

/**
 * 题目：
 * 给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，
 * 该子序列中相邻元素之间的差等于 difference 。
 * 子序列是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。
 * <p>
 * 示例：
 * 输入：arr = [1,2,3,4], difference = 1
 * 输出：4
 * 解释：最长的等差子序列是 [1,2,3,4]。
 */

public class Test75_最长定差子序列 {
    public static int longestSubsequence(int[] arr, int difference) {
        int ans = 0;
        Map<Integer, Integer> dp = new HashMap<Integer, Integer>();
        for (int v : arr) {
            dp.put(v, dp.getOrDefault(v - difference, 0) + 1);
            ans = Math.max(ans, dp.get(v));
        }
        return ans;
    }
    

    public static void main(String[] args) {
        int[] test = new int[]{4, 3, 2, 1};
        int i = longestSubsequence(test, 1);
        System.out.println(i);
    }
}
